/**
 * @param {number[]} stones
 * @return {boolean}
 */
var canCross = function (stones) {
  let len = stones.length,
    dp = new Array(stones.length);
  for (let i = 0; i < len; i++) {
    dp[i] = new Array(stones[0].length).fill(false);
  }
  dp[0][0] = true;
  for (let i = 1; i < len; i++) {
    if (stones[i] - stones[i - 1] > i) {
      return false;
    }
  }
  for (let i = 1; i < len; i++) {
    for (let j = i - 1; j >= 0; j--) {
      let k = stones[i] - stones[j];
      // 两个石头之间距离超过下标就不可能跨过去
      if (k > j + 1) {
        break;
      }
      // 注意这里每次到达i位置且之前跳过k个石头是通过三种情况进行判断的
      dp[i][k] = dp[j][k - 1] || dp[j][k] || dp[j][k + 1];
      // 如果到达终点且可以跳到
      if (i == len - 1 && dp[i][k]) {
        return true;
      }
    }
  }
  return false;
};
let stones = [0, 1, 3, 5, 6, 8, 12, 17];
console.log(canCross(stones));
stones = [0, 1, 2, 3, 4, 8, 9, 11];
console.log(canCross(stones));
stones = [0, 1, 2, 3, 4, 5, 6, 12];
console.log(canCross(stones));
